#pragma once

#include <vector>
#include <hash_map>
#include <map>
#include "AST.h"
#include "Follow.h"
#include "Parent.h"
#include "CFG.h"
#include "Next.h"

#include "Type.h"
#include "PatternType.h"
#include "TreeNodeType.h"

#include "VarTable.h"
#include "ProcTable.h"
#include "NodeTable.h"
#include "EntityTable.h"
#include "ConstantTable.h"
#include "Uses.h"
#include "Modifies.h"
#include "CommonParent.h"
#include "Calls.h"

#include "Utilities.h"

class PKB {

private:
	typedef bool isPartialMatch;

	AST myAST;
	Follow myFollowsTable;		
	Parent myParentTable;
	Calls myCallsTable;
	Next myNextTable;
	Next myNextBipTable;
	hash_map<Type::Index::Proc,CFG*> myCFGFamily;

	Modifies myModifyTable;
	Uses myUseTable;
	CommonParent myCommonParent;

	VarTable myVarTable;		
	ProcTable myProcTable;
	NodeTable myNodeTable;
	ConstantTable myConstantTable;
	EntityTable myEntityTable;

	//Star Bit Maps Flags
	bool myParentStarBitMapFlag;
	bool myFollowStarBitMapFlag;
	bool myCallStarBitMapFlag;

	//Star Bit Maps
	Type::Map::Bit myParentStarBitMap;
	Type::Map::Bit myFollowStarBitMap;
	Type::Map::Bit myCallStarBitMap;

	// last line of while map
	Type::Map::Line myLastWhileMap;
	Type::Map::Line myLastIfMap;

	// Map for fast retrieval of isProcAWall (if it exists in here)
	// to be set during isProcAWall() function itself
	// keyed by a string "procName varName"
	std::map<std::string, bool> isProcAWallMap;

	// Map for fast retrieval of the lines which a proc exits to
	std::map<Type::Index::Proc, std::vector<Type::Index::Line>> procExitToIndexesMap;

	static bool instanceFlag;
	static PKB *myPKB;

	void getChildStarHelper(Type::Index::Line, Type::List::Line *);
	void getCallStarHelper(int, vector<int>*, vector<int> (PKB::*innerFunction)(int),PKB*);
	void getCallerLineOfStarHelper(Type::Index::Proc, vector<int>*,vector<int>*);
	void getNextStarHelper(int, vector<int>*, vector<int> (PKB::*innerFunction)(int), PKB*, bool);
	
	int getNumOfExitPoints(Type::Index::Proc);
	bool isExitPoint(Type::Index::Line);
	
	Type::List::Line filterLineIndexByLineEntityType(Type::List::Line, Type::Entity::Line);

	Type::Index::Line getMin(Type::List::Line);
	Type::Index::Line getMax(Type::List::Line);
	bool isCommExist(Type::List::Line, Type::List::Line);
	bool commonParentSetFlag;
	bool isNextStarFast(Type::Index::Line a, Type::Index::Line b);
	bool isNextStarSlow(Type::Index::Line a, Type::Index::Line b);

	/**-------------------------------------------------
	 *	Helper functions written by Yu De 
	 *-------------------------------------------------*/
	// Returns true if the given proc, starting from the first line, has no possible path through which
	// it does not modify the given var, and false if it has at least one such possible path.
	// A proc is a wall if it has a wall line in it.
	// IMPORTANT: currently dependent on nextModified and lastOfIf for speed.
	bool isProcAWall(const Type::Index::Proc proc, const Type::Index::Var var);
	// Returns true if the given line 'definitely modifies' the given var, and false otherwise.
	// Here, 'definitely modifies' means the following:
	// For ASSIGN: if it modifies the var.
	// For CALL: if the procedure called by this line is a wall.
	// For WHILE: can always exit the while immdeiately, so it can't be a wall.
	// For IF: if there is a wall line in BOTH its then and else direct stmt lists.
	// IMPORTANT: currently dependent on nextModified and lastOfWhile and lastOfIf for speed
	bool isLineAWall(const Type::Index::Line line, const Type::Index::Var var);
	// Returns true if the line exists in the pkb.
	bool isLineExists(Type::Index::Line line);
	// Returns the commonIf line of x and y using the getCommon function in PKB.
	// At the same time, also sets the hasCommonIf, xInThen, and yInThen boolean values.
	Type::Index::Line findCommonIf(Type::Index::Line x, Type::Index::Line y, bool* hasCommonIfPtr, bool* xInThenPtr, bool* yInThenPtr);
	// Returns the commonWhile line of x and y using the getCommon function in PKB.
	// At the same time, also sets the hasCommonWhile boolean value.
	Type::Index::Line findCommonWhile(Type::Index::Line x, Type::Index::Line y, bool* hasCommonWhilePtr);

	// Yu De's
	Type::List::Line getLineIndexesForPattern(PatternType, Type::Index::Var, 
		TreeNode*, TreeNode*, bool, bool);
	bool matchSubtreePerfectly(TreeNode*, TreeNode*);
	bool matchSubtreePartially(TreeNode*, TreeNode*);

	// This function should only be called from matchSubtreePartially!!!
	bool matchSubtreePartiallyWithoutRecursion(TreeNode*, TreeNode*);
	TreeNodeType lineEntityTypeToTreeNodeType(Type::Entity::Line);
	// Above, Yu De's method for pattern matching

	// Ryan's method
	bool setLastLineOfContainer(Type::Entity::Line, Type::Index::Line, Type::List::Line&);
	const Type::List::Line& getPossibleAffectLinesFrom(bool, Type::Index::Line);
	Type::List::Line& getAffects(bool, bool, Type::Index::Line);
	bool recurAffects(bool, bool, bool, Type::Index::Line, Type::Index::Line, Type::Set::Line&, Type::List::Line&);
	const Type::List::Line& getPossibleAffectBipLinesFrom(bool, Type::Index::Line);
	Type::List::Line& getAffectsBip(bool, bool, Type::Index::Line);
	bool recurAffectsBip(bool, bool, bool, Type::Index::Line, Type::Index::Line, Type::Set::Line&, Type::List::Line&);


	// debug method
	void PKB::printAllIsReachable();

public:
	PKB(void);
	~PKB(void);
	void clear();
	static PKB* getInstance();
	static void initializeInstance();

	/* Yu De's debugging functions */
	// Function for debugging isProcAWall
	void printAllWallProcs();
	// Function for debugging isLineAWall
	void printAllWallLines();
	// Function for debugging getProcExitToIndexes
	void printAllProcExitToIndexes();

	///getFirstSibling returns itself if it is the first child of it's parent
	Type::Index::Line getFirstSibling(Type::Index::Line);
	///getLastSibling returns itself if it is the last child of it's parent
	Type::Index::Line getLastSibling(Type::Index::Line);
	/**************CFG****************/
	/*!
	Whenever we meet a new procedure, we create a CFG.
	To create CFG: 
	1, Create a CFG by procedure index.
	2, Add the returned CFG to CFGFamily in PKB.
	3, Create a CFG Node by the first line index in current procedure and this line's corresponding AST Tree Node.
	4, Set the returned CFG Node as the root of CFG just created.
	5, Continue to create CFG Node
	6, Link the previous CFG Node to the returned CFG Node accordingly. (Special case for WHILE and IF)
	7, Repeat Step 5 and 6 until the end of the procedure.
	8, Create an End Node.
	9, Link all the CFG Nodes which might be the end of the procedure to this returned End Node. (Special case for WHILE and IF)  
	*/
	virtual CFG* createCFG(Type::Index::Proc);
	virtual void setCFGRoot(CFG*, CFGNode*);
	virtual CFGNode* getCFGRootNode(CFG*);
	virtual CFGNode* getCFGEndNode(CFG*);
	virtual void addToCFGFamily(CFG*);
	virtual CFG* getCFGByProcedureIndex(Type::Index::Proc);

	///create CFGNode with its contents and coresponding AST node.
	virtual CFGNode* createCFGNode(Type::Index::Line, TreeNode*);
	///create CFG End Node which has a content equals to -2
	virtual CFGNode* createCFGEndNode();

	///the first CFGNode will become the predecessor of the second CFGNode. and the Second CFGNode will become the successor of the first CFG Node.
	virtual bool linkCFGNodes(CFGNode*, CFGNode*);

	///get a CFGNode's corresponding ASTNode
	virtual TreeNode* getASTNodeFromCFG(CFGNode*);
	///get the content in the CFGNode. The content refers to the line index.
	virtual Type::Index::Line getCFGNodeContent(CFGNode*);

	///return a list of CFGNode pointers which are the successors of given CFGNode
	virtual vector<CFGNode*> getSuccessorsCFG(CFGNode*);
	///return a list of CFGNode pointers which are the predecessors of given CFGNode
	virtual vector<CFGNode*> getPredecessorCFG(CFGNode*);

	/****************NextBip**************/
	///set NextBip relation
	bool setNextBip(Type::Index::Line, Type::Index::Line);
	///return a list of line which is NextBip to the given line. eg NextBip(1,2), NextBip(1,3) getSuccessorNextBip(1) will return 2,3
	Type::List::Line getSuccessorNextBip(Type::Index::Line);
	///return a list of line which the given line is NextBip to. eg NextBip(2,4), NextBip(3,4) getPredecessorNextBip(4) will return 2,3
	Type::List::Line getPredecessorNextBip(Type::Index::Line);
	///return true if the given two line index have NextBip relation. eg NextBip(1,2) isNextBip(1,2) will return true
	bool isNextBip(Type::Index::Line, Type::Index::Line);
	///return true if the given line index has some line that is after it
	bool hasSuccessorNextBip(Type::Index::Line);
	///return true if the given line index has some line that is before it
	bool hasPredecessorNextBip(Type::Index::Line);

	///return a list of line which are on the control flow after given line
	Type::List::Line getSuccessorNextBipStar(Type::Index::Line);
	/// Written by Yu De. Returns a list of line which are on the control flow after given line
	Type::List::Line getSuccessorNextBipStar_Yude(Type::Index::Line line);
	///return a list of line which are on the control flow before given line
	Type::List::Line getPredecessorNextBipStar(Type::Index::Line);
	///return true if the given two line index have NextBip star relation.
	bool isNextBipStar(Type::Index::Line, Type::Index::Line);

	virtual bool setNextBipBitMap(Type::Map::Bit);

	virtual bool isNextBipBitMapSet();

	/* Helper functions for finding exit points and for getting proc exit-to indexes,
	 * useful for nextBIP setting and affectsBIP
	 * Written by Yu De */
	// Gets the line indices to which the given procedure may return to (if it is called by another procedure).
	// May be empty if this procedure does not exit to and lines.
	// IMPORTANT: Requires first that next and calls is set.
	Type::List::Line getProcExitToIndexes(Type::Index::Proc proc);

	/****************Next**************/
	///set next relation
	bool setNext(Type::Index::Line, Type::Index::Line);
	///return a list of line which is next to the given line. eg Next(1,2), Next(1,3) getSuccessorNext(1) will return 2,3
	Type::List::Line getSuccessorNext(Type::Index::Line);
	///return a list of line which the given line is next to. eg Next(2,4), Next(3,4) getPredecessorNext(4) will return 2,3
	Type::List::Line getPredecessorNext(Type::Index::Line);
	///return true if the given two line index have next relation. eg Next(1,2) isNext(1,2) will return true
	bool isNext(Type::Index::Line, Type::Index::Line);
	///return true if the given line index has some line that is after it
	bool hasSuccessorNext(Type::Index::Line);
	///return true if the given line index has some line that is before it
	bool hasPredecessorNext(Type::Index::Line);

	///return a list of line which are on the control flow after given line
	Type::List::Line getSuccessorNextStar(Type::Index::Line);
	///return a list of line which are on the control flow before given line
	Type::List::Line getPredecessorNextStar(Type::Index::Line);
	///return true if the given two line index have next star relation.
	bool isNextStar(Type::Index::Line, Type::Index::Line);

	virtual bool setNextBitMap(Type::Map::Bit);

	virtual bool isNextBitMapSet();

	/****************AST**************/

	///create TreeNode* which only has a type, like "lineLst", "+". 
	TreeNode* createTreeNode(TreeNodeType);
	///create TreeNode* which has a type and content. The content is the index of the a Line or var.
	TreeNode* createTreeNode(TreeNodeType, int);

	void setRoot(TreeNode*);
	TreeNode* getRoot();

	///add the second TreeNode* as the child of the first TreeNode*
	///and add the first TreeNode* as parent of the second TreeNode*
	void linkNodes(TreeNode*,TreeNode*);
	void linkNodesFront(TreeNode*,TreeNode*);

	///return true is the type of TreeNode* matches with the given TreeNodeType
	bool matchesNodeType(TreeNode*, TreeNodeType);

	///return the content inside the node
	int getContentStoredIn(TreeNode*);

	///return a list of Index::Line that match the pattern type, varRefIndex and subtree partially or fully in the entire program
	//return a list of Index::Line that match the pattern type, varRefIndex and subtree partially or fully
	//in the entire program
	virtual Type::List::Line getLineIndexForPattern(PatternType, Type::Index::Var, TreeNode*, isPartialMatch);

	//return a list of stmtIndex that match the pattern type, varRefIndex and subtree partially or fully
	//in the specific procedure
	//Type::List::Line getStmtIndexForPattern(Type::Index::Proc, PatternType, Type::Index::Var, TreeNode*, isPartialMatch);

	/****************ConstantTable**************/

	/// insert constant with the given line and entity , returns status of operation.
	bool insertConstant(Type::Index::Line, Type::Entity::Line, Type::Constant);

	/// get all constants
	virtual const Type::List::Constant& getConstants();
	/// get the list of constants at the given Line
	const Type::List::Constant& getConstantsAtLine(Type::Index::Line);

	/// get the list of lines where the given constant appeared in
	const Type::List::Line& getLinesOfConstant(Type::Constant);
	/// get the list of lines with the given entity type where the given constant appeared in
	const Type::List::Line& getLinesOfConstant(Type::Constant, Type::Entity::Line);

	/// check for constant existence with the given constant
	bool isConstantExists(Type::Constant);

	/****************VarTable**************/

	/// Insert variable with its name, return variable index
	Type::Index::Var insertVar(Type::Name::Var);

	/// get all variable indices
	virtual const Type::List::Var& getVarIndices();
	/// get variable index with the given variable name
	virtual Type::Index::Var getVarIndex(Type::Name::Var);
	/// get variable name with the given variable index
	virtual Type::Name::Var getVarName(Type::Index::Var);

	/// check for variable existence with the given variable name
	bool isVarExists(Type::Name::Var);
	/// check for variable existence with the given variable index
	bool isVarExists(Type::Index::Var);

	/****************ProcTable**************/

	/// insert procedure with its name, return procedure index
	Type::Index::Proc insertProc(Type::Name::Proc);
	/// insert procedure with its starting & ending line index
	bool insertProcStartEnd(Type::Index::Proc, Type::Index::Line, Type::Index::Line);

	/// get all procedure indices
	virtual const Type::List::Proc& getProcIndices();
	/// get procedure index with the given procedure name
	virtual Type::Index::Proc getProcIndex(Type::Name::Proc);
	/// get procedure name with the given procedure index
	virtual Type::Name::Proc getProcName(Type::Index::Proc);
	/// get starting & ending line of the given procedure index
	virtual Type::Pair::StartEnd getProcStartEnd(Type::Index::Proc);
	/// get the procedure index where the given line is located at
	Type::Index::Proc getProcIndexOfLine(Type::Index::Line);

	/// check for procedure existence with the given procedure name
	bool isProcExistInProcTable(Type::Name::Proc);
	/// check for procedure existence with the given procedure index
	bool isProcExistInProcTable(Type::Index::Proc);

	///set the exit points of a proc
	bool setProcExitPoint(Type::Index::Proc, Type::Index::Line);

	///get the exit points of a proc. return empty list if none.
	const Type::List::Line& getProcExitPoints(Type::Index::Proc);

	/****************EntityTable**************/

	/// Insert entity with the given Line & procedure/statement, returns status of operation.
	bool insertLineEntity(Type::Index::Line, Type::Entity::Line);
	/// set the last line (with child* property) of the given while with the given line
	bool setLastOfWhile(Type::Index::Line, Type::Index::Line);
	/// set the last lines (with child* property) of the given if with the given line for then and else parts
	bool setLastOfIf(Type::Index::Line, Type::Index::Line, Type::Index::Line);

	/// get all entities
	const Type::List::LineEntity& getLineEntities();
	/// get entity with the given Line
	Type::Entity::Line getLineEntityByLine(Type::Index::Line);

	/// get all lines
	const Type::List::Line& getLines();
	/// get the list of lines associated with the given entity
	virtual const Type::List::Line& getLinesByEntity(Type::Entity::Line);

	/// get the last line (with child* property) of the given while
	Type::Index::Line getLastOfWhile(Type::Index::Line);
	/// get the last lines, namely then and else, (with child* property) of the given if
	const Type::List::Line& getLastOfIf(Type::Index::Line);

	/// check if the given line matches the given entity
	bool isLineEntity(Type::Index::Line, Type::Entity::Line);

	/*******************NodeTable********************/

	/// Insert reference of node with the given Line, returns status of operation
	bool insertNode(Type::Index::Line, TreeNode*);

	/// get node with the given Line
	TreeNode* getNodeByLine(Type::Index::Line);

	/// get the list of lines associated with the given reference of node
	Type::Index::Line getLineByNode(TreeNode*);

	/****************Follow**************/

	///the second Type::Index::Line follows the first Type::Index::Line
	void setFollows(Type::Index::Line,Type::Index::Line);

	///get the Type::Index::Line which follows the given Type::Index::Line. If none is found return -1.
	//get the Type::Index::Line which follows the given Type::Index::Line
	//If none is found return -1.
	virtual Type::Index::Line getFollows(Type::Index::Line);

	///get the Type::Index::Line which is followed by the given Type::Index::Line. If none is found return -1.
	//get the Type::Index::Line which is followed by the given Type::Index::Line
	//If none is found return -1.
	virtual Type::Index::Line getFollowedBy(Type::Index::Line);

	///return true if the second Type::Index::Line follows the first Type::Index::Line
	virtual bool isFollows(Type::Index::Line, Type::Index::Line);

	/*! 
	return a set of lines which follows the given line directly or indirectly
	e.g. Follows(1,2), Follows(2,3), Follows(3,4) -> getFollowsStar(1) = {2,3,4}
	if none is found, return an empty vector
	*/
	virtual Type::List::Line getFollowStar(Type::Index::Line);

	/*!
	return a set of lines which has the given line entity type and follows the given line  directly or indirectly
	e.g. Follows(1,2), Follows(2,3), Follows(3,4) where 4 is while statement-> getFollowsStar(1, WHILE_LINE_ENTITY) = {4}
	if none is found, return an empty vector
	*/
	virtual Type::List::Line getFollowStar(Type::Index::Line, Type::Entity::Line);

	/*! 
	return a set of lines which is followed by the given line directly or indirectly
	e.g. Follows(1,2), Follows(2,3), Follows(3,4) -> getFollowedByStar(4) = {1,2,3}
	if none is found, return an empty vector
	*/
	virtual Type::List::Line getFollowedByStar(Type::Index::Line);

	/*! 
	return a set of lines which has the given line entity type and is followed by the given line directly or indirectly
	e.g. Follows(1,2), Follows(2,3), Follows(3,5) where 2, 3 are while statement -> getFollowedByStar(5, WHILE_LINE_ENTITY) = {2,3} 
	if none is found, return an empty vector
	*/
	virtual Type::List::Line getFollowedByStar(Type::Index::Line, Type::Entity::Line);

	///return true if the seconde Type::Index::Line follows the first Type::Index::Line directly or indirectly
	virtual bool isFollowStar(Type::Index::Line, Type::Index::Line);

	virtual bool setFollowBitMap(Type::Map::Bit);

	virtual bool isFollowBitMapSet();

	virtual bool setFollowStarBitMap(Type::Map::Bit);

	virtual bool isFollowStarBitMapSet();

	/****************Parent**************/

	///Set the first Type::Index::Line as the parent of the second Type::Index::Line
	void setParent(Type::Index::Line, Type::Index::Line);

	//void setParent(Type::Index::Line, Type::Entity::Line, Type::Index::Line);

	/*!
	return a set of Type::Index::Line which are the direct child of the given Type::Index::Line
	if none is found, return an empty vector
	*/
	virtual Type::List::Line getChild(Type::Index::Line);

	/*!
	return a set of Type::Index::Line which are of the given LineEntity Type and are the direct child of the given Type::Index::Line
	if none is found, return an empty vector
	*/
	virtual Type::List::Line getChild(Type::Index::Line, Type::Entity::Line);

	/*!
	return the direct parent of the given Type::Index::Line
	if none is found, return -1
	*/
	virtual Type::Index::Line getParent(Type::Index::Line);

	///return true if given Type::Index::Line has parent
	virtual bool hasParent(Type::Index::Line);

	///return true if given Type::Index::Line has parent and this parent has the given line entity type
	virtual bool hasParent(Type::Index::Line, Type::Entity::Line);

	///return true if given Type::Index::Line has child
	virtual bool hasChild(Type::Index::Line);

	///return true if given Type::Index::Line has child which this child has the given line entity type
	virtual bool hasChild(Type::Index::Line, Type::Entity::Line);

	///return true if the first Type::Index::Line is the direct Parent of the second Type::Index::Line
	virtual bool isParent(Type::Index::Line,Type::Index::Line);

	/*!
	return a set of Type::Index::Line which are the direct or indirect child of the given Type::Index::Line
	if none is found, return an empty vector
	*/
	virtual Type::List::Line getChildStar(Type::Index::Line);

	/*!
	return a set of Type::Index::Line which are of the given LineEntity type and are the direct or indirect child of the given Type::Index::Line
	if none is found, return an empty vector
	*/
	virtual Type::List::Line getChildStar(Type::Index::Line, Type::Entity::Line);

	/*!
	return a set of Type::Index::Line which are the direct or indirect parent of the given Type::Index::Line
	if none is found, return an empty vector
	*/
	virtual Type::List::Line getParentStar(Type::Index::Line);

	/*!
	return a set of Type::Index::Line which are of the given LineEntity type and are the direct or indirect parent of the given Type::Index::Line
	if none is found, return an empty vector
	*/
	virtual Type::List::Line getParentStar(Type::Index::Line, Type::Entity::Line);

	/*!
	return true if the first Type::Index::Line is the direct or indirect Parent of the second Type::Index::Line
	*/
	virtual bool isParentStar(Type::Index::Line, Type::Index::Line);

	virtual bool setParentBitMap(Type::Map::Bit);

	virtual bool isParentBitMapSet();

	virtual bool setParentStarBitMap(Type::Map::Bit);

	virtual bool isParentStarBitMapSet();

	/****************Modifies**************/

	/*!
	Set modifies relationship for the given line, entity, variable, 
	returns status of operation
	*/
	bool setLineModifies(Type::Index::Line, Type::Entity::Line, Type::Index::Var);
	/*! 
	Set modifies relationship for the given proc, variable, 
	returns status of operation
	*/
	bool setProcModifies(Type::Index::Proc, Type::Index::Var);
	/*! 
	set the bitmap (square matrix) for line modifies relationship, 
	returns status of operation
	*/
	bool setLineModifiesBitMap(Type::Map::Bit);
	/*!
	set the bitmap (square matrix) for proc modifies relationship, 
	returns status of operation
	*/
	bool setProcModifiesBitMap(Type::Map::Bit);

	/// get all modified variables
	const Type::List::Var& getModifiedVars();
	/// get the variable modified by the given line
	const Type::List::Var& getModifiedVarsByLine(Type::Index::Line);
	/// get the variable modified by the given proc
	const Type::List::Var& getModifiedVarsByProc(Type::Index::Proc);

	/// get the list of lines that modifies the given variable
	const Type::List::Line& getLinesModify(Type::Index::Var);
	/// get the list of lines with given entity that modifies the given variable
	const Type::List::Line& getLinesModify(Type::Index::Var, Type::Entity::Line);
	/// get the list of procs that modifies the given variable
	const Type::List::Proc& getProcsModify(Type::Index::Var);

	/// check if the given line modifies the given variable 
	virtual bool isLineModifies(Type::Index::Line, Type::Index::Var);
	/// check if the given proc modifies the given variable 
	virtual bool isProcModifies(Type::Index::Proc, Type::Index::Var);

	/****************Uses**************/

	/*! 
	Set uses relationship for the given line, entity, variable,
	returns status of operation
	*/
	bool setLineUses(Type::Index::Line, Type::Entity::Line, Type::Index::Var);
	/*! 
	Set uses relationship for the given proc,, variable,
	returns status of operation
	*/
	bool setProcUses(Type::Index::Proc, Type::Index::Var);
	/*!
	set the bitmap (square matrix) for line uses relationship, 
	returns status of operation
	*/
	bool setLineUsesBitMap(Type::Map::Bit);
	/*!
	set the bitmap (square matrix) for proc uses relationship, 
	returns status of operation
	*/
	bool setProcUsesBitMap(Type::Map::Bit);

	/// get all used variables
	const Type::List::Var& getUsedVars();
	/// get the list of variables used by the given line
	const Type::List::Var& getUsedVarsByLine(Type::Index::Line);
	/// get the list of variables used by the given proc
	const Type::List::Var& getUsedVarsByProc(Type::Index::Proc);

	/// get the list of lines that uses the given variable
	const Type::List::Line& getLinesUse(Type::Index::Var);
	/// get the list of lines with given entity that uses the given variable
	const Type::List::Line& getLinesUse(Type::Index::Var, Type::Entity::Line);
	/// get the list of procs that uses the given variable
	const Type::List::Proc& getProcsUse(Type::Index::Var);

	/// check if the given Line uses the given variable 
	virtual bool isLineUses(Type::Index::Line, Type::Index::Var);
	/// check if the given Line uses the given variable 
	virtual bool isProcUses(Type::Index::Proc, Type::Index::Var);

	/****************************Affects****************************************/

	/*!
	set the bitmap (square matrix) for line-variable of the line 
	where the variable was last modified, 
	returns status of operation
	*/
	bool setLastModified(Type::Map::LineMatrix&);
	/*!
	set the bitmap (square matrix) for line-variable of the line 
	where the variable is going to be modified next, 
	returns status of operation
	*/
	bool setNextModified(Type::Map::LineMatrix&);
	/*!
	set the bitmap (square matrix) for parent-parent of common parent between 2 parents, 
	returns status of operation
	*/
	bool setCommon(Type::Entity::Line, Type::Map::ParentMatrix&);
	/*! 
	get the common parent of parent 1 and 2
	0 is returned when there is no common parent between 1 and 2
	-1 is returned when parent 1 or 2 does not exist in the record
	*/
	Type::Index::Line getCommon(Type::Entity::Line, Type::Index::Line, Type::Index::Line);

	/// return the list of lines that the given line affects directly
	Type::List::Line& getAffects(Type::Index::Line);
	/// return the list of directly affected lines by the given line
	Type::List::Line& getAffected(Type::Index::Line);
	/// check if the given line 1 directly affects the given line 2
	bool isAffects(Type::Index::Line, Type::Index::Line);

	/// return the list of lines that the given line affects indirectly
	Type::List::Line& getAffectsStar(Type::Index::Line);
	/// return the list of indirectly affected lines by the given line
	Type::List::Line& getAffectedStar(Type::Index::Line);
	/// check if the given line 1 indirectly affects the given line 2
	bool isAffectsStar(Type::Index::Line, Type::Index::Line);

	/****************AffectBip**************/
	/// return the list of lines that affectBip directly the given line (all x such that affectsBIP(x,givenLine))
	Type::List::Line& getAffectBip(Type::Index::Line);
	/// return the list of directly affectedBip lines by the given line (all y such that affectsBIP(givenLine,y))
	Type::List::Line& getAffectedBip(Type::Index::Line);
	/// check if the given line 1 directly affectBip the given line 2
	bool isAffectBip(Type::Index::Line, Type::Index::Line);

	/* Written by Yu De, for AFFECTSBIP */
	// Recursive helper function for getAffectBip
	void getAffectBip_Recursive(const Type::Index::Line line, const std::unordered_map<Type::Index::Var, bool>& usedVarsMap, 
									std::unordered_map<Type::Index::Line, bool>* traversedMap, 
									const std::unordered_map<Type::Index::Line, bool>& predecessorBipStarMap,
									Type::List::Line* results);
	/// Checks if line x affects line y (branching into procedures if necessary)
	bool isAffectBip_Yude(Type::Index::Line x, Type::Index::Line y);
	// Checks if there is a direct route straight down from x to y.
	// Definition: x has a direct route in its proc to y which does not modify v iff
	//	1. x and y are in the same proc
	//	2. x < y AND has no common if, OR x < y AND has a common if BUT are in the same then/else
	//	3. there exists some control path that only contains lines in {x, ... ,y} such that v is not modified 
	//  by any ASSIGN or CALL (for sure) along this path (except for y, and x if it is an ASSIGN)
	bool hasDirectRouteInProc(Type::Index::Line x, Type::Index::Line y, Type::Index::Var v);
	// Checks if there is a direct route straight down from x to y. (includeX/includeY set-able)
	// VERY similar to hasDirectRouteInProc except that x == y is acceptable and considered 'reached' 
	// as long as either includeX or includeY are false.
	bool isReachable(Type::Index::Line x, Type::Index::Line y, Type::Index::Var v, bool includeX, bool includeY);
	// Checks if there is a path such that we can exit the proc x is in, starting from x, without modifying v.
	// includeX/includeExitPoint is set-able.
	bool checkCanExitProc(Type::Index::Line x, Type::Index::Var v, bool includeX, bool includeExitPoint);
	// Checks if there is a loop back route from x to y that may use a while loop to loop back
	// or may exit the proc through its exit points and possibly come back through a call stmt
	// calling the proc which x is in.
	// Definition: x has a loop back route to y which does not modify v iff
	//	hasDirectRouteInProc(x,y,v) OR...
	//	1. x and y are in the same proc
	//	2. x < y AND has common if AND are in different stmtlsts of the common if,
	//		OR x >= y
	//	3. there exists some control path by either a while loop or by exiting the proc X,
	//		and finally coming back to proc X again through a call stmt somewhere.
	bool hasLoopBackRoute(Type::Index::Line x, Type::Index::Line y, Type::Index::Var v);
	// Checks if there is a route by going out of the procedure from x using reachable
	// call stmts and exit points, in order to reach y.
	// Definition: x has an out route to y which does not modify v iff
	// hasLoopBackRoute(x,y,v) which will only work if x and y are in the same procs, OR...
	// 1. x and y are in different procs
	// 2. there exists some control path starting from x by using reachable call stmts and exit points
	//		from x in order to reach y.
	bool hasOutRoute(Type::Index::Line x, Type::Index::Line y, Type::Index::Var v);
	// For debugging: prints out all the (x,y,v) triplets that satisfy hasDirectRouteInProc(x,y,v)
	void printAllHasDirectRouteInProc();
	// For debugging: prints out all the (x,y,v) triplets that satisfy isReachable(x,y,v)
	void printAllIsReachable(bool includeX, bool includeY);
	// For debugging: prints out all the (x,y,v) triplets that satisfy hasLoopBackRoute(x,y,v)
	void printAllHasLoopBackRoute();
	// For debugging: prints out all the (x,y,v) triplets that satisfy hasOutRoute(x,y,v)
	void printAllHasOutRoute();

	/// return the list of lines that the given line affectBip indirectly
	Type::List::Line& getAffectBipStar(Type::Index::Line);
	/// return the list of indirectly affectedBip lines by the given line
	Type::List::Line& getAffectedBipStar(Type::Index::Line);
	/// check if the given line 1 indirectly affectBip the given line 2
	bool isAffectBipStar(Type::Index::Line, Type::Index::Line);
	
	/****************Calls**************/
	/*!
	Set the first Proc calls the second Proc, with the specific line index who calls the second proc.
	return false, if not set successfully
	*/
	bool setCalls(Type::Index::Proc, Type::Index::Line, Type::Index::Proc);

	/*!
	return a list of all procedure indices called by a specified procIndex
	if none, return an empty vector
	eg. Calls(1,2) Calls(1,3) ---> getCalledBy(1) will return 2,3
	*/
	Type::List::Proc getCalledBy(Type::Index::Proc);

	/*!
	return a list of all procedure indices called by a specified lineIndex
	if none, return an -1
	eg. Calls(1,2) and line 5 in procefure 1 calls procedure 2.---> getCalledByLine(5) will return 2
	*/
	Type::Index::Proc getCalledByLine(Type::Index::Line);

	/*!
	return a list of all procedure indices that call a specified procIndex
	if none, return an empty vector
	eg. Calls(1,3) Calls(2,3) ---> getCallerOf(3) will return 1,2
	*/
	Type::List::Proc getCallerOf(Type::Index::Proc);

	/*!
	return a list of all line indices that call a specified procIndex
	if none, return an empty vector
	eg. Calls(1,3) Calls(2,3) where line 5, line 8 in procedure 1 and line 9 in procedure 2 call procedure 3 ---> getCallerLineOf(3) will return 5,8,9
	*/
	Type::List::Line getCallerLineOf(Type::Index::Proc);

	///return true if the first Proc calls the second Proc
	bool isCalls(Type::Index::Proc, Type::Index::Proc);
	Type::List::Line getCallStmtsInProc(Type::Index::Proc);
	//Call* relation
	/*!
	return a list of all procedure indices called by a specified procIndex directly or indirectly
	if none, return an empty vector
	eg. Calls*(1,2) Calls*(1,3) ---> getCalledByStar(1) will return 2,3
	*/
	vector<Type::Index::Proc> getCalledByStar(Type::Index::Proc);

	/*return a list of all procedure indices called by a specified lineIndex directly or indirectly
	if none, return an -1
	eg. Calls*(1,2) and line 5 in procefure 1 calls procedure 2 directly or indirectly.---> getCalledByLine(5) will return 2
	*/
	Type::List::Proc getCalledByLineStar(Type::Index::Line);

	/*!
	return a list of all procedure indices that call a specified procIndex directly or indirectly
	if none, return an empty vector
	eg. Calls*(1,3) Calls*(2,3) ---> getCallerOfStar(3) will return 1,2
	*/
	vector<Type::Index::Proc> getCallerOfStar(Type::Index::Proc);

	/*!
	return a list of all line indices that call a specified procIndex directly or indirecly
	if none, return an empty vector
	eg. Calls*(1,3) Calls*(2,3) where line 5, line 8 in procedure 1 and line 9 in procedure 2 call procedure 3 directly or indirectly ---> getCallerLineOf(3) will return 5,8,9
	*/
	vector<Type::Index::Line> getCallerLineOfStar(Type::Index::Proc);

	///return true if the first Proc calls the second Proc directly or indirectly
	bool isCallsStar(Type::Index::Proc, Type::Index::Proc);

	///return true if the bit map for call relation is set
	bool setCallsBitMap(Type::Map::Bit);

	virtual bool setCallStarBitMap(Type::Map::Bit);

	virtual bool isCallStarBitMapSet();
};